//
//  RestoreIpAddresses.swift
//  LeetCodeSummary
//
//  Created by WangYonghe on 2020/6/19.
//  Copyright © 2020 WangYonghe. All rights reserved.
//  93.复原IP地址   中等

import UIKit

/*
 给定一个只包含数字的字符串，复原它并返回所有可能的 IP 地址格式。

 有效的 IP 地址正好由四个整数（每个整数位于 0 到 255 之间组成），整数之间用 '.' 分隔。

  

 示例:

 
 输入: "25525511135"
 输出: ["255.255.11.135", "255.255.111.35"]
 */

class RestoreIpAddresses: NSObject {
    
    var resultStr = [String]()
    
    func restoreIpAddresses(_ s: String) -> [String] {
        if s.count < 4 || s.count > 12 {
            return []
        }
        
        self.dfs(0, [], s)
        
        return resultStr
    }
    
    func dfs(_ startIndex: Int, _ tmpArr: [String], _ soureString:String){
        
        var arr = tmpArr
        
        print(arr)
        
        print(">>>>>>>>>>>>>>>>>>>\(startIndex)")
        
        if arr.count > 1 {
            if Int(arr[0])! < 10 && soureString.count > 10 {
                return
            }
            if Int(arr[0])! > 10 && Int(arr[0])! < 100 && soureString.count > 11{
                return
            }
        }
        
        if arr.count == 4 {
            if startIndex == soureString.count {
                resultStr.append(arr.joined(separator: "."))
            }
            return
        }
        
        
        for index in 1 ..< 4 {
            //
            if startIndex+index > soureString.count{

                print("break")
                break
            }
            
            let star = soureString.index(soureString.startIndex, offsetBy: startIndex)
            let end = soureString.index(soureString.startIndex, offsetBy: startIndex + index)
        
            let subString:String = String(soureString[star ..< end])
            print("\(subString)")
            if subString.hasPrefix("0") && subString.count > 1 || (index == 3) && Int(subString)! > 255{
                print("continue")
                continue
            }
            
            arr.append(subString)
  
            self.dfs(startIndex+index, arr, soureString)
            
            arr.removeLast()
            
        }
    }

}
